home *** CD-ROM | disk | FTP | other *** search
- \bigskip
- {\magonebf 5.1 Directed graphs (graph)}
-
- {\bf 1. Definition}
-
- An instance $G$ of the data type $graph$ consists of a list of nodes $V$ and a
- list of edges E ($node$ and $edge$ are predefined data types). Every edge $e\in
- E$ is a pair of nodes $(v,w) \in V\times V$, $v$ is called the source of $e$ and
- $w$ is called the target of $e$. With every node $v$ the list of its adjacent
- edges $adj\_list(v) = \{\ e \in E\ | source(e) = v\ \}$, called the adjacency
- list of $v$, is associated.
-
- \def\name{$graph$}
- \def\type{graph}
-
- \bigskip
- {\bf 2. Creation}
-
- \create G {}
-
- creates an instance $G$ of type $graph$ and initializes it to the
- empty graph.
-
-
- \bigskip
- {\bf 3. Operations}
-
- {\bf a) Access operations}
- \+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr
- \+\op int indeg {node\ v}
- {returns the indegree of node $v$}
- \smallskip
- \+\op int outdeg {node\ v}
- {returns the outdegree of node $v$}
- \smallskip
- \+\op node source {edge\ e}
- {returns the source node of edge $e$}
- \smallskip
- \+\op node target {edge\ e}
- {returns the target node of edge $e$}
- \smallskip
- \+\op int number\_of\_nodes { }
- {returns the number of nodes in $G$ }
- \smallskip
- \+\op int number\_of\_edges { }
- {returns the number of edges in $G$ }
- \smallskip
- \+\op list\<node\> all\_nodes { }
- {returns the list $V$ of all nodes of $G$}
- \smallskip
- \+\op node first\_node { }
- {returns the first node in $V$}
- \smallskip
- \+\op node last\_node { }
- {returns the last node in $V$}
- \smallskip
- \+\op node succ\_node {node\ v}
- {returns the successor of node $v$ in $V$ }
- \+\nop {(nil if it does not exist)}
- \smallskip
- \+\op node pred\_node {node\ v}
- {returns the predecessor of node $v$ in $V$ }
- \+\nop {(nil if it does not exist)}
- \smallskip
- \+\op list\<edge\> all\_edges { }
- {returns the list $E$ of all edges of $G$}
- \smallskip
- \+\op edge first\_edge { }
- {returns the first edge in $E$}
- \smallskip
- \+\op edge last\_edge { }
- {returns the last edge in $E$}
- \smallskip
- \+\op edge succ\_edge {edge\ e}
- {returns the successor of edge $e$ in $E$ }
- \+\nop {(nil if it does not exist)}
- \smallskip
- \+\op edge pred\_edge {edge\ e}
- {returns the predecessor of edge $e$ in $E$ }
- \+\nop {(nil if it does not exist)}
- \smallskip
- \+\op list\<edge\> adj\_edges {node\ v}
- {returns the list of all edges adjacent to $v$}
- \smallskip
- \+\op list\<node\> adj\_nodes {node\ v}
- {returns the list of all nodes adjacent to $v$}
- \smallskip
- \+\op edge first\_adj\_edge {node\ v}
- {returns the first edge in the adjacency list of $v$}
- \smallskip
- \+\op edge last\_adj\_edge {node\ v}
- {returns the last edge in the adjacency list of $v$}
- \smallskip
- \+\op edge adj\_succ {edge\ e}
- {returns the successor of edge $e$ in the }
- \+\nop {adjacency list of $source(e)$ }
- \+\nop {(nil if it does not exist)}
- \smallskip
- \+\op edge adj\_pred {edge\ e}
- {returns the predecessor of edge $e$ in the }
- \+\nop {adjacency list of $source(e)$}
- \+\nop {(nil if it does not exist)}
- \smallskip
- \+\op edge cyclic\_adj\_succ {edge\ e}
- {returns the cyclic successor of edge $e$ in the}
- \+\nop {adjacency list of $source(e)$}
- \smallskip
- \+\op edge cyclic\_adj\_pred {edge\ e}
- {returns the cyclic predecessor of edge $e$ in the}
- \+\nop {adjacency list of $source(e)$}
- \smallskip
- \+\op node choose\_node {}
- {returns a node of $G$ (nil if $G$ is empty)}
- \smallskip
- \+\op edge choose\_edge {}
- {returns an edge of $G$ (nil if $G$ is empty)}
-
- \bigskip
- {\bf b) Update operations}
- \medskip
- \+\op node new\_node {}
- {adds a new node to $G$ and returns it}
- \smallskip
- \+\op void del\_node {node\ v}
- {deletes $v$ and all edges adjacent to $v$}
- \+\nop {from $G$. \precond{$indeg(v) = 0$}.}
- \smallskip
- \+\op edge new\_edge {node\ v,\ w}
- {adds a new edge $(v,w)$ to $G$ by appending }
- \+\nop {it to the adjacency list of $v$ and returns it.}
- \smallskip
- \+\op edge new\_edge {edge\ e,\ node\ w,\ rel\_pos\ dir=after} {}
- \+\nop {adds a new edge $e\' = (source(e),w)$ to $G$ by }
- \+\nop {inserting it after ($dir$=after) or before ($dir$}
- \+\nop {=before) edge $e$ into the adjacency list of }
- \+\nop {$source(e)$, returns $e\'$.}
- \smallskip
- \+\op void del\_edge {edge\ e}
- {deletes the edge $e$ from $G$}
- \smallskip
- \+\op void del\_all\_nodes {}
- {deletes all nodes from $G$ }
- \smallskip
- \+\op void del\_all\_edges {}
- {deletes all edges from $G$ }
- \smallskip
- \+\op edge rev\_edge {edge\ e}
- {reverses the edge $e = (v,w)$ by removing it }
- \+\nop {from $G$ and inserting the edge $e\' = (w,v)$ }
- \+\nop {into $G$ by appending it to the adjacency list}
- \+\nop {of $w$, returns $e\'$ }
- \smallskip
- \+\op void rev {}
- {all edges in $G$ are reversed}
- \smallskip
- \+\op void sort\_nodes {int (*cmp)(node\&,\ node\&)} {}
- \+\nop {the nodes of $G$ are sorted according to the}
- \+\nop {ordering defined by the comparing function}
- \+\nop {$cmp$. Subsequent executions of forall\_nodes}
- \+\nop {step through the nodes in this order.}
- \+\nop { (cf.~TOPSORT1 in section 8.1)}
- \smallskip
- \+\op void sort\_nodes {node\_array\<T\>\ A} {}
- \+\nop {the nodes of $G$ are sorted according to the}
- \+\nop {entries of node\_array $A$ (cf.~section 5.7)}
- \+\nop {\precond $T$ must be linearly ordered}
- \smallskip
- \+\op void sort\_edges {int (*cmp)(edge\&,\ edge\&)} {}
- \+\nop {the edges of $G$ are sorted according to the}
- \+\nop {ordering defined by the comparing function}
- \+\nop {$cmp$. Subsequent executions of forall\_edges}
- \+\nop {step through the edges in this order.}
- \+\nop { (cf.~TOPSORT1 in section 8.1)}
- \smallskip
- \+\op void sort\_edges {edge\_array\<T\>\ A} {}
- \+\nop {the edges of $G$ are sorted according to the}
- \+\nop {entries of edge\_array $A$ (cf.~section 5.7)}
- \+\nop {\precond $T$ must be linearly ordered}
- \smallskip
- \+\op list\<edge\> insert\_reverse\_edges {} {}
- \+\nop {for every edge $(v,w)$ in $G$ the reverse edge}
- \+\nop {$(w,v)$ is inserted into $G$. The list of all}
- \+\nop {inserted edges is returned.}
- \smallskip
- \+\op void make\_undirected {}
- {every edge $(v,w)$ in $G$ is inserted into the}
- \+\nop {adjacency list of $w$.}
- \smallskip
- \+\op void make\_directed {}
- {every edge $(v,w)$ in $G$ is removed from the}
- \+\nop {adjacency list of $w$.}
- \smallskip
- \+\op void clear {}
- {makes $G$ the empty graph}
-
- \vfill\eject
-
- \bigskip
- {\bf c) Iterators}
- \medskip
- With the adjacency list of every node $v$ is associated a list iterator
- called the adjacency iterator of $v$ (cf.~list). There are operations to
- initialize, move, and read these iterators. They are used to implement
- iteration statements (forall\_adj\_edges, forall\_adj\_nodes).
- \bigskip
- \+\op void init\_adj\_iterator {node\ v}
- {assigns nil to the adjacency iterator of node $v$}
- \smallskip
- \+\op bool current\_adj\_edge {edge\&\ e,\ node\ v} {}
- \+\nop {if the adjacency iterator of $v$ is defined ($\ne$ nil)}
- \+\nop {its contents is assigned to $e$ and true is returned}
- \+\nop {else false is returned.}
- \smallskip
- \+\op bool next\_adj\_edge {edge\&\ e,\ node\ v} {}
- \+\nop {moves the adjacency iterator of $v$ forward (to the}
- \+\nop {first item of $adj\_list(v)$ if it is nil) and returns}
- \+\nop {$G$.current\_adj\_edge($e,v$)}
- \smallskip
- \+\op bool current\_adj\_node {node\&\ w,\ node\ v} {}
- \+\nop {if $G$.current\_adj\_edge($e$, $v$) = true then assign}
- \+\nop {$target(e)$ to w and return true, else return}
- \+\nop {false}
- \smallskip
- \+\op bool next\_adj\_node {node\&\ w,\ node\ v} {}
- \+\nop {if $G$.next\_adj\_edge($e$, $v$) = true then assign}
- \+\nop {$target(e)$ to w and return true, else return}
- \+\nop {false}
- \smallskip
- \+\op void reset {}
- {assign nil to all adjacency iterators in $G$}
-
- \bigskip
- {\bf d) Miscellaneous operations}
- \medskip
- \+\op void write {ostream\ O\ =\ cout}
- {writes a compressed representation of $G$ to }
- \+\nop {the output stream $O$.}
- \smallskip
- \smallskip
- \+\op void write {string\ s}
- {writes a compressed representation of $G$ to }
- \+\nop {the file with name $s$.}
- \smallskip
- \+\op void read {istream\ I\ =\ cin}
- {reads a compressed representation of $G$ from }
- \+\nop {the input stream $I$.}
- \smallskip
- \+\op void read {string\ s}
- {reads a compressed representation of $G$ from }
- \+\nop {the file with name $s$.}
- \smallskip
- \+\op void print\_node {node\ v,\ ostream\ O = cout} {}
- \+\nop {writes a readable representation of node $v$ to }
- \+\nop {the output stream $O$}
- \smallskip
- \+\op void print\_edge {edge\ e,\ ostream\ O = cout} {}
- \+\nop {writes a readable representation of edge $e$ to}
- \+\nop {the output stream $O$}
- \smallskip
- \+\op void print {ostream\ O = cout}
- {writes a readable representation of $G$ to the}
- \+\nop {output stream $O$}
-
-
- \bigskip
- {\bf 4. Iteration}
-
- {\bf forall\_nodes}($v,G$)
- $\{$ ``the nodes of $G$ are successively assigned to $v$" $\}$
-
- {\bf forall\_edges}($e,G$)
- $\{$ ``the edges of $G$ are successively assigned to $e$" $\}$
-
- {\bf forall\_adj\_edges}($e,w$) \nl
- \phantom{{\bf forall\_edges}($v,G$)}
- $\{$ ``the edges adjacent to node w are successively assigned to e" $\}$
-
- {\bf forall\_adj\_nodes}($v,w$) \nl
- \phantom{{\bf forall\_edges}($v,G$)}
- $\{$ ``the nodes adjacent to node w are successively assigned to v" $\}$
-
- \bigskip
- {\bf 5. Implementation}
-
- Graphs are implemented by doubly linked adjacency lists. Most operations
- take constant time, except of all\_nodes, all\_edges, del\_all\_nodes,
- del\_all\_edges, clear, write, and read which take time $O(n+m)$, where
- $n$ is the current number of nodes and $m$ is the current number of edges.
- The space requirement is $O(n+m)$.
-
-
